The background description provided herein is for the purpose of generally presenting the context of the disclosure. Work of the presently named inventors, to the extent it is described in this background section, as well as aspects of the description that may not otherwise qualify as prior art at the time of filing, are neither expressly nor impliedly admitted as prior art against the present disclosure.
The discovery of some sparse structure in matrix (i.e., two-dimensional) data is an integral part of many applications, such as those involving collaborative filtering or image inpainting. For matrices, the sparse structure is reflected by the matrix rank and finding sparse structure can be formulated as a matrix completion problem. For example, user-movie ratings generated by a movie rental service can be represented as an incomplete matrix. Missing elements of this incomplete matrix can be inferred based on a low-rank structure of the incomplete matrix. In this manner, the movie rental service can predict user movie preferences.
Existing matrix completion methods typically depend on Singular Value Decomposition (SVD). However, when data is represented in more than two dimensions (e.g., color images, image plus depth-map data, time-dependent user product ratings, etc.), SVD methods are not directly applicable. Further, known generalizations of SVD to more than two dimensions, such as Higher-Order SVD (HOSVD) and Canonical Polyadic Decomposition (CPD), are not strictly consistent with SVD and prevent the generalization of common algorithms.